1. Field of the Invention
The present invention relates to an improved queuing method for implementing weighted round-robin (WRR) scheduling for high-speed packet switching and routing.
2. Related Art
Queuing and scheduling are two critical function blocks that are used by today's packet switches and routers to support quality of services (QoS). A typical packet switch/router has multiple ports forwarding and receiving data packets. Usually a data packet enters a switch/router from one port and departs from another port. The switch/router ports can each receive and forward data packet simultaneously.
FIG. 1 is a block diagram of a high-level switch/router architecture 100 that includes switch ports 101-108 and switch/router 110. Switch/router 110 includes line cards 111-118 and switch fabric 120. Data packets arrive at the left hand side switch ports 101-104 (i.e., ingress ports) and are provided to the corresponding line cards 111-114. The data packets are then processed by switch fabric 120, and then depart from the right hand side ports 105-108 (i.e., egress ports) via line cards 115-118.
During normal operation, multiple packets may be received from several ingress ports and leave switch/router 110 on one egress port. These packets must be queued in front of the egress port to wait for an opportunity to be forwarded.
FIG. 2 is a block diagram of line card 115, which includes multiple queues 2011-201N for storing data packets received from ingress ports 101-104, and scheduler 210. Each of queues 2011-201N is controlled by scheduler 210. Based on QoS requirements, scheduler 210 selects one of queues 2011-201N to send data packets over the egress port 105.
Different queuing and scheduling algorithms are implemented in switches and routers to meet various QoS requirements. The simplest is the First-In-First-Out (FIFO) scheme where packets are stored in one queue and sent in the same order as they are received. The drawback of the FIFO scheme is that bandwidth is not distributed fairly among all of the traffic flows. A few aggressive flows can seize most of the bandwidth. To solve this problem, a per-flow queue based scheduling algorithm, called the round-robin (RR) scheduling scheme, has been introduced. The idea of round-robin scheduling, in essence, is that traffic from different flows are queued separately in their own queues and the switch/router port scheduler circularly and repeatedly “visits” all the packet queues, and sends one packet from each queue during the visit. In terms of distributing bandwidth among different flows, round-robin scheduling is a fairer solution than FIFO scheduling because each flow can be guaranteed the opportunity to send a packet in each round-robin scheduling cycle.
However, round-robin scheduling has two problems. The first problem is that this scheme cannot differentiate large packets from small packets. When a flow sends a packet ten times larger than packets sent by other flows, this flow uses ten times more bandwidth than the other flows. To be fair, the packet length has to be taken into consideration in the scheduling algorithm. In addition, in real network environments, different flows can have different bandwidth requirements and should not be treated as equal. In other words, each flow is given a weighting factor and the bandwidth should be distributed to all the flows proportional to their weights. Weighted round-robin (WRR) scheduling is based on the round-robin scheduling algorithm, but also incorporates a technique for distributing the bandwidth according to the weights of the various flows.
There are different ways of implementing weighted round-robin scheduling. One popular approach is to provide transmit opportunities to each flow on a periodic, cyclic basis, as with round-robin scheduling, but instead of only accepting one packet, multiple packets from each queue can be forwarded. The number of packets transmitted is determined in response to the weight assigned to the flow. For instance, a queue with a weight equal to 2 can have two packets forwarded, while a queue with a weight of 10 can have 10 packets forwarded during each visit by the scheduler. This method is relatively simple to implement. Although this method is efficient at processing backlogged queues, it has the negative effect of forwarding the packets from each flow in a clumped manner (e.g., 10 packets at a time) rather than a smooth manner (e.g., 1 packet at a time).
The real problem with the above-described weighted round-robin scheduling is that it fails to work properly when the network is not heavily loaded. For example, assume that there are 64K flow queues. Further assume that the first queue has a weight equal to 10, while all of the other queues have a weight equal to 1. Ten packets are supposed to be sent from the first queue, and one packet is supposed to be sent from each of the other queues during each visit by the scheduler. If there is only one packet waiting in the first queue, the scheduler will forward this packet, and then move to service the other queues. Suppose that more packets arrive in the first queue after the scheduler has left the first queue. The scheduler cannot come back to the first queue until after the scheduler has visited each of the other (64K−1) queues. During the described round-robin cycle, only one packet is forwarded from the first queue (i.e., the same number as is forwarded for each of the other queues). In this case, the first queue does not receive ten times the bandwidth of the other queues, as suggested by the weight of the first queue.
It would therefore be desirable to have an improved technique for solving the above-described deficiencies of conventional weighted round-robin scheduling.